{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Linked List Nth to Last Node - SOLUTION\n",
    "\n",
    "## Problem Statement\n",
    "Write a function that takes a head node and an integer value **n** and then returns the nth to last node in the linked list. For example, given:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Node:\n",
    "\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.nextnode  = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "a = Node(1)\n",
    "b = Node(2)\n",
    "c = Node(3)\n",
    "d = Node(4)\n",
    "e = Node(5)\n",
    "\n",
    "a.nextnode = b\n",
    "b.nextnode = c\n",
    "c.nextnode = d\n",
    "d.nextnode = e\n",
    "\n",
    "# This would return the node d with a value of 4, because its the 2nd to last node.\n",
    "target_node = nth_to_last_node(2, a) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "target_node.value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution\n",
    "\n",
    "One approach to this problem is this:\n",
    "\n",
    "Imagine you have a bunch of nodes and a \"block\" which is n-nodes wide. We could walk this \"block\" all the way down the list, and once the front of the block reached the end, then the other end of the block would be a the Nth node!  \n",
    "\n",
    "So to implement this \"block\" we would just have two pointers a left and right pair of pointers. Let's mark out the steps we will need to take:\n",
    "\n",
    "* Walk one pointer **n** nodes from the head, this will be the right_point\n",
    "* Put the other pointer at the head, this will be the left_point\n",
    "* Walk/traverse the block (both pointers) towards the tail, one node at a time, keeping a distance **n** between them.\n",
    "* Once the right_point has hit the tail, we know that the left point is at the target.\n",
    "\n",
    "Let's see the code for this!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def nth_to_last_node(n, head):\n",
    "\n",
    "    left_pointer  = head\n",
    "    right_pointer = head\n",
    "\n",
    "    # Set right pointer at n nodes away from head\n",
    "    for i in xrange(n-1):\n",
    "        \n",
    "        # Check for edge case of not having enough nodes!\n",
    "        if not right_pointer.nextnode:\n",
    "            raise LookupError('Error: n is larger than the linked list.')\n",
    "\n",
    "        # Otherwise, we can set the block\n",
    "        right_pointer = right_pointer.nextnode\n",
    "\n",
    "    # Move the block down the linked list\n",
    "    while right_pointer.nextnode:\n",
    "        left_pointer  = left_pointer.nextnode\n",
    "        right_pointer = right_pointer.nextnode\n",
    "\n",
    "    # Now return left pointer, its at the nth to last element!\n",
    "    return left_pointer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Test Your Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ALL TEST CASES PASSED\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "RUN THIS CELL TO TEST YOUR SOLUTION AGAINST A TEST CASE \n",
    "\n",
    "PLEASE NOTE THIS IS JUST ONE CASE\n",
    "\"\"\"\n",
    "\n",
    "from nose.tools import assert_equal\n",
    "\n",
    "a = Node(1)\n",
    "b = Node(2)\n",
    "c = Node(3)\n",
    "d = Node(4)\n",
    "e = Node(5)\n",
    "\n",
    "a.nextnode = b\n",
    "b.nextnode = c\n",
    "c.nextnode = d\n",
    "d.nextnode = e\n",
    "\n",
    "####\n",
    "\n",
    "class TestNLast(object):\n",
    "    \n",
    "    def test(self,sol):\n",
    "        \n",
    "        assert_equal(sol(2,a),d)\n",
    "        print 'ALL TEST CASES PASSED'\n",
    "        \n",
    "# Run tests\n",
    "t = TestNLast()\n",
    "t.test(nth_to_last_node)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Good Job!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
